/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 87111
 * Date: 2025-09-16
 * Time: 18:27
 */
public class BinarySearchTree {
    static class Node {
        public Node left;
        public int val;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }
    //头结点
    public Node root;

    //查找
    public boolean searchNode(int key) {
        if(root == null) {
            return false;
        }
        Node tmpRoot = root;
        while(tmpRoot != null) {
            if(key > tmpRoot.val) {
                tmpRoot = tmpRoot.right;
            }else if(key < tmpRoot.val) {
                tmpRoot = tmpRoot.left;
            }else {
                return true;
            }
        }
        return false;
    }

    //插入
    public void insertNode(int key) {
        if(root == null) {
            root = new Node(key);
            return;
        }
        Node tmpRoot = root;
        Node parent = null;
        while(tmpRoot != null) {
            if(key > tmpRoot.val) {
                parent = tmpRoot;
                tmpRoot = tmpRoot.right;
            }else if(key < tmpRoot.val) {
                parent = tmpRoot;
                tmpRoot = tmpRoot.left;
            }else {
                return;
            }
        }
        Node tmp = new Node(key);
        if(parent.val > key) {
            parent.left = tmp;
        }
        if(parent.val < key) {
            parent.right = tmp;
        }
    }

    //删除
    public void remove(int key) {
        Node parent = null;
        Node newRoot = root;
        while(newRoot != null) {
            if(key > newRoot.val) {
                parent = newRoot;
                newRoot = newRoot.right;
            }else if(key < newRoot.val) {
                parent = newRoot;
                newRoot = newRoot.left;
            }else {
                //删除
                removeNode(newRoot,parent);
            }
        }
    }

    /**
     * 删除结点的具体实现
     * @param cur 被删除的结点
     * @param parent 被删除结点的父亲结点
     */
    private void removeNode(Node cur, Node parent) {
        //删除的结点左边没有结点
        if(cur.left == null) {
            if(cur == root) {
                root = root.right;
            }else if(cur == parent.right) {
                parent.right = cur.right;
            }else {
                parent.left = cur.right;
            }
        }else if(cur.right == null) {
            if(cur == root) {
                root = root.left;
            }else if(cur == parent.right) {
                parent.right = cur.left;
            }else {
                parent.left = cur.left;
            }
        }else {
            //删除结点的左右两边都不为空
            Node tmpParent = cur;
            Node tmp = cur.right;
            while(tmp.left != null) {
                tmpParent = tmp;
                tmp = tmp.left;
            }
            //此时找到右边树的最小值的结点
            cur.val = tmp.val;
            if(tmp == tmpParent.right) {
                tmpParent.right = tmp.right;
            }else {
                tmpParent.left = tmp.right;
            }
        }
    }


}
